#!/usr/bin/env python

# calcule_cdr is part of code.google.com/camtools, copyright 2006 Camille Huot
# and is licensed under http://www.gnu.org/copyleft/gpl.html

# Documentation:
# calcule_cdr has been written to choose which OGG Vorbis albums needs to be
# burnt to maximise the CD-R capacity.
# Run calcule_cdr in a directory containing several directories to be burnt and
# you'll get the list of what you've to burn to maximise the CD-R.
# Example:
#
# cam@poseidon /data/audio/NEW $ ls
# Amon_Amarth_-_With_Oden_On_Our_Side-by.tko@bullys-metalworld.co.uk/
# Anthropia_-_The_Ereyn_Chronicles_Part1-The_Journey_of_Beginnings-2006-www.zonaheavymetal.com/
# Armageddon-Crossing_the_Rubicon/
# Autopsy-Jardins_de_Saint_Estève/
# Autopsy-Un_autre/
# Bloodsimple-2005-A_Cruel_World/
# BVoozers_Inc-Live_Insa/
# Chinchilla_-_Take_no_prisoners_-_last_upload_by_strypermagic_2004_-/
# Death-1987-Scream_Bloody_Gore/
# Death-1988-Leprosy/
# Death-1990-Spiritual_Healing/
# Death-1991-Human/
# Death-1993-Individual_Thought_Patterns/
# Death-1995-Symbolic/
# Death-1998-The_Sound_Of_Perseverance/
# Death-2001-Live_in_Eindhoven/
# Death-2001-Live_In_L.A/
# Death_Angel/
# Dragonland-Astronomy-Promo-2006-AMRC/
# Fairyland_-_The_Fall_Of_An_Empire_-_2006_-_www.zonaheavymetal.com/
# Fantomas-1999_-_Amenaza_al_Mundo/
# Fantomas-2001_-_The_Director's_Cut/
# Fantomas-2005_-_Suspended_Animation/
# Infectious_Groove/
# Megadeth-1990-Rust_In_Peace/
# Megadeth-1992-Countdown_To_Extinction/
# Pantera-1990-Cowboys_From_Hell/
# Ramones_-_(2002)_Loud,_Fast_Ramones_-_Their_Toughest_Hits/
# SYMBYOSIS_-_Crisis/
# Symbyosis-On_the_Wings_of_Phoenix-2CD-2005-AMRC/
# SYMBYOSIS_-_The_Fluid/
# Testament_-_Live_At_The_Fillmore_(VBR)_[QbiC]/
#
# cam@poseidon /data/audio/NEW $ calcule_cdr
# Symbyosis-On_the_Wings_of_Phoenix-2CD-2005-AMRC
# SYMBYOSIS_-_The_Fluid
# Ramones_-_(2002)_Loud,_Fast_Ramones_-_Their_Toughest_Hits
# Fairyland_-_The_Fall_Of_An_Empire_-_2006_-_www.zonaheavymetal.com
# Testament_-_Live_At_The_Fillmore_(VBR)_[QbiC]
# Death-2001-Live_in_Eindhoven
# Death-2001-Live_In_L.A


# if there are more than max_dir directories, we switch from optimal to
# heuristic algorithm. do some bench to find your best value.
# optimal algorithm: best solution, take time if there is too much data
# heuristic algorithm: always fast but not always the best solution
max_dir = 19

# CD-R size, in MB
cdr = 700

### CODE

import os, string
from copy import copy

list = {}
for line in os.popen('/bin/du -sk *').readlines():
  (size, label) = string.split(line)
  list[int(size)] = label

cdr *= 1024
best = [0, 0]

def possible_best(combinaison):
	somme = 0
	for element in combinaison:
		somme += element
	if somme < cdr and somme > best[0]:
		best[0] = somme
		best[1] = combinaison

def enum(A, B):
	possible_best(A)
	for b in copy(B):
		B.remove(b)
		enum(A + [b], copy(B))

def quick(liste):
	liste.sort()
	liste.reverse()
	best[1] = []
	for each in liste:
		if best[0] + each < cdr:
			best[0] += each
			best[1].append(each)

if len(list.keys()) < max_dir:
	enum([], list.keys())
else:
	quick(list.keys())

for i in best[1]:
	print list[i]
